/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 //用辅助数组记录
// class Solution {
// public:
//     bool isPalindrome(ListNode* head) {
//         vector<int> nums;
//         ListNode* cur = head;
//         while (cur)
//         {
//             nums.push_back(cur->val);
//             cur = cur->next;
//         }

//         int left = 0, right = nums.size() - 1;
//         while (left <= right)
//         {
//             if (nums[left] != nums[right])
//                 return false;
            
//             left++;
//             right--;
//         }
//         return true;
//     }
// };

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head)
            return head;
        ListNode* newHead = head;
        ListNode* headNext = newHead->next;
        
        while (headNext)
        {
            ListNode* tmp = headNext->next;
            headNext->next = newHead;
            newHead = headNext;
            headNext = tmp;
        }
        head->next = nullptr;
        return newHead;
        
    }

    bool isPalindrome(ListNode* head) {
        if (head->next == nullptr)
            return true;
        
        //先找到链表的中间部分
        //如果链表长度为奇数，那么中间节点作为链表的后半部分
        bool ret = true;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* slow_prev;
        while (fast && fast->next)
        {
            slow_prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }

        slow_prev->next = nullptr;  //将链表分成两半

        //反转后半部分链表
        //将前一半和后一半对比
        ListNode* newHead = reverseList(slow);
        ListNode* curA = head;
        ListNode* curB = newHead;
        ListNode* tail;
        while (curA && curB)
        {
            if (curA->val != curB->val)
                ret = false;

            tail = curA;
            curA = curA->next;
            curB =  curB->next; 
        }
        //恢复链表
        tail->next = reverseList(newHead);
        return ret;
    }
};